package com.fps.webshop.question.question_others;

/**
 * 皇后问题
 * NUMBER = 4 --> 2
 * NUMBER = 5 --> 10
 * NUMBER = 6 --> 4
 * NUMBER = 7 --> 40
 * NUMBER = 8 --> 92
 * NUMBER = 9 --> 352
 * NUMBER = 10 --> 724
 * NUMBER = 11 --> 2680
 * NUMBER = 12 --> 14200
 * NUMBER = 13 --> 73712
 * @author kingdee
 *
 */
public class TheQueenQuestion {
	//定义棋盘大小
	final static int NUMBER = 13;
	
	//数组记录皇后摆放的
	int queen[] = new int[NUMBER];
	
	//记录解法数量（包含旋转棋盘重复）
	int count = 0;
	
	public static void main(String[] args) {
		TheQueenQuestion queen = new TheQueenQuestion();
    	queen.eightQueen(0);
    	System.out.println("总共有 " +queen.count+ " 摆放方法");
	}
    
	private void eightQueen(int currentColumn) {
		//这个for循环的目的是尝试讲皇后放在当前列的每一行
		for(int row=0;row<NUMBER;row++) {
			//判断当前列的row行是否能放置皇后
			if(isLegal(row,currentColumn)) {
		        //放置皇后
				queen[currentColumn] = row;
				if(currentColumn!=(NUMBER-1)) {
					//摆放下一列的皇后
					eightQueen(currentColumn+1);
				
				}else {
					//递归结束，此时count要++了
					count++;
					
					//输出当前棋盘皇后的拜访位置
					/*
					 * for(Integer a : queen) { System.out.print((a+1)+" "); }
					 * System.out.println(" ");
					 */
				}
			}
		}
	}
	
	/**
     * 判断当（currentRow,currentColumn)是否可以放置皇后
     * @param currentColumn 
     * @return
     */
    public boolean isLegal(int currentRow,int currentColumn) {
    	//遍历前面几列
    	for(int preColumn=0;preColumn<currentColumn;preColumn++) {
    		int row = queen[preColumn];
    		//说明在子preColumn的低currentRow已经有了皇后
    		if(row==currentRow) {
    			return false;
    		}
    		
    	    //行与行的差值
            int rowDiff= Math.abs(row -currentRow);
          
            //列于列的差值
            int columnDiff =  Math.abs(currentColumn-preColumn);
            //说明斜线上有皇后
            if(rowDiff==columnDiff ){
                return false;
            }
    	}
    	
    	//说明（currentRow,currentColumn)可以摆放。
    	return true;
    }


}
